home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6806 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.6 KB
  1. Path: uni-erlangen.de!winx03!sunshine!schoof
  2. From: schoof@informatik.uni-wuerzburg.de (Jochen Schoof)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Followup-To: comp.lang.c
  6. Date: 15 Feb 1996 10:16:54 GMT
  7. Organization: University of Wuerzburg, Germany
  8. Message-ID: <4fv16m$cuj@winx03.informatik.uni-wuerzburg.de>
  9. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com>
  10. NNTP-Posting-Host: wi2x01.informatik.uni-wuerzburg.de
  11. X-Newsreader: TIN [version 1.2 PL2]
  12.  
  13. John Cleland (clelaj@born.com) wrote:
  14. : The Crow wrote:
  15. : > 
  16. : > Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  17. : > given factorial.  For instance,
  18. : > 
  19. : > 5! = 120
  20. : > 
  21. : > so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  22. : > Problem is, no matter how huge of a data-type you use, there isn't any way
  23. : > for
  24. : > the computer to handle 1000!, it is however possible to find the last 
  25. : > non-zero
  26. : > digit somehow.  One thing I have tried is as I went through mulitplying the
  27. : > series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the
  28. : > trailing ZEROS, I got this to work up to 789, but it wont work with 1000 
  29. : > and i
  30. : > am not really sure why.  If anyone has a clue how I can do this let me know.
  31.  
  32. You might want to use a library that provides arbitrary length precision
  33. when in need of computations like 1000! The computer can really do a lot 
  34. if only you provide the right programs :-)
  35.  
  36. : Don't just strip the trailing zeros, remove all digits except the last 
  37. : non-zero
  38. : digit (which is your output) and then multiply by the next number in 
  39. : your sequence.
  40. : This keeps the numbers down to a managable level and gives the correct 
  41. : answer as
  42. : no more significant digit can affect the value of the LSD.
  43. :
  44. : If we have a function int LSD(int val) which computes the value of the least
  45. : significant non-zero digit the pseudo C code should be something like :
  46. :
  47. : int factLSD = 1;
  48. : int i;
  49. :
  50. : for (i = 1; i <= 1000; i++)
  51. :   {
  52. :   factLSD = LSD(i * factLSD);
  53. :   print i, factLSD;
  54. :   } 
  55.  
  56. Sorry, but this technique does NOT work as can be proven easily:
  57.  
  58.  14! equals 87178291200 which results in its LSD being 2
  59.  
  60. The function above (after being ported to legal C) tells us the LSD
  61. of 15! must be 3, but in fact
  62.  
  63.  15! equals 1307674368000 which results in its LSD being 8
  64.  
  65. in contradiction to what your function said. It is not sufficient
  66. to only keep track of the very last relevant digit. The problem
  67. mentioned above can be avoided when storing the last two relevant
  68. digits and I believe this technique finally is sufficient and 
  69. still alows to compute the digits for faculties far beyond 1000.
  70. Thus the following function should work as desired:
  71.  
  72. int factorial_lsd(int n)
  73. {
  74.   int result=1, i;
  75.  
  76.   if(n>1) 
  77.     for(i=1;i<=n;i++)
  78.     {
  79.       result*=i;
  80.       while(result%10==0) result/=10;
  81.       result%=100;
  82.     }
  83.   return temp%10;
  84. }
  85.  
  86. Hope this helps...
  87.  
  88. - Jochen
  89.  
  90. PS: I did not provide my little mathematical analysis of the
  91.     required multiplications, because they are a little boring.
  92.  
  93. --
  94. --------------------------------------------------------------------------
  95.  Jochen Schoof                  mailto:schoof@informatik.uni-wuerzburg.de
  96.  Lehrstuhl fuer Informatik II +-------------------------------------------
  97.  Universitaet Wuerzburg       | You are just reading a .sig-light:
  98.  D-97074 Wuerzburg (Germany)  | It is free of fat, sugar and cholesterol!
  99. ------------------------------+-------------------------------------------
  100.  WWW-Homepage:        http://www.informatik.uni-wuerzburg.de/staff/joscho
  101. --------------------------------------------------------------------------
  102.